use crate::to_mut_ref;

/// 字符串算法题

/// 最长公共前缀
pub fn longest_common_prefix(strs: Vec<String>) -> String {
    let result = strs.iter().min_by(|a, b| a.len().cmp(&b.len())).unwrap().to_owned();
    if result.is_empty() { return result; }
    for i in 0..result.len() {
        let x = &result.as_str()[i..=i];
        if !strs.iter().all(|s| x.eq(&s.as_str()[i..=i])) {
            return result.as_str()[0..i].to_owned();
        }
    }
    result
}

/// 最长回文子串
/// dp(i,j) = s的i-j的子串
/// dp(i,j) = s(i)==s(j) && dp(i+1,j-1)
pub fn longest_palindrome(s: String) -> String {
    let str = s.as_str();
    let len = str.len();
    if len < 2 {
        return str.to_owned();
    }
    let mut dp: Vec<Vec<bool>> = Vec::new();
    for i in 0..len {
        let mut tmp = vec![false; len];
        tmp[i] = true;
        dp.push(tmp);
    }
    let mut ri = 0;//左边起始索引
    let mut l = 1;//总长度
    for i in 1..len {
        for j in 0..i {
            if str[i..=i].ne(&str[j..=j]) {
                dp[j][i] = false;
            } else {
                if i - j < 3 {
                    dp[j][i] = true;
                } else {
                    dp[j][i] = dp[j + 1][i - 1];
                }
            }
            if dp[j][i] && i - j + 1 >= l {
                l = i - j + 1;
                ri = j;
            }
        }
    }
    str[ri..ri + l].to_owned()
}

/// 翻转字符串里的单词
pub fn reverse_words(s: String) -> String {
    fn rev_words(ss: &str, a1: usize, a2: usize, b1: usize, b2: usize) {
        let rev_str = |ss: &str| {
            let x = ss.as_bytes();
            for i in 0..x.len() / 2 {
                std::mem::swap(to_mut_ref!(&x[i],u8), to_mut_ref!(&x[x.len()-i-1],u8));
            }
        };
        rev_str(&ss[a1..=a2]);
        rev_str(&ss[b1..=b2]);
        rev_str(&ss[a1..=b2]);
    }

    "".to_owned()
}

#[test]
fn test_longest_common_prefix() {
    let vec1 = vec!["cir", "car"];
    let vec_string: _ = vec1.into_iter().map(|e| String::from(e)).collect();
    let string = longest_common_prefix(vec_string);
    println!("{string}");
}

#[test]
fn test_longest_palindrome() {
    let string = "abdbaba";

    let sstr = longest_palindrome(string.to_owned());
    println!("{sstr}");
}

#[test]
fn test_reverse_words() {
    let test = "the sky is blue";
    let string = reverse_words(test.to_owned());
    println!("{string}");
}

#[test]
fn test_() {
    let mut string = "123 asd".to_owned();
    println!("{string}");
}